package dlx

// import "fmt"

// Knuth's link-list object
type node struct {
	head                  *header
	up, down, left, right *node
	row                   *node
}

// Knuth's column header object
type header struct {
	node
	size, value int
}

// DLX object which holds whole matrix and result
type dlx struct {
	aCols         []header // all column headers
	root          *header  // aCols[0]
	result        []*node  // result
	totalSolution int      // total Solution
	solutionSet   []string
}

func SolveAll(input string) (int, []string) {

	/*	Condition 1: Cell taken
		The are 9x9 = 81 possible cells that can be taken (a cell is "taken" after you place a number in it) so first condition yields 81 (matrix)columns of (r,c) kind. R will be the major index for this condition.
		So, (matrix)columns from 1 to 9 will represent putting a number in row 1, columns 1 to 9.
		(Matrix)columns from 10 to 18 will represent putting a number in row 2, columns 1 to 9 and so on...
		Basically if you want to place a number in row r, column c you will place a 1 in column r*9+c.

		Condition 2: Row, digit condition
		There are 9 rows and 9 possible different numbers you can place in each row so, 9x9 = 81 and we have again 81 (matrix)columns for condition 2. Also this time r is being the major index so placing digit d in row r will place a 1 in (matrix)column r*9+d +[81].
		81 are the first condition related columns.

		Condition 3: Column, digit condition
		As for the rows, there are 9 columns with 9 possible different numbers you can place each one of them.
		Again, 9x9 = 81 (matrix)columns and this time the column index is the major one, so placing digit d in column c will place a 1 at (matrix)column c*9+d +[81]+[81].
		81+81 are the first + second condition related columns.

		Condition 4: Box, digit condition
		As for rows and columns, same for the boxes. 9 boxes, 9 digits, 81 more (matrix)columns. Box index is the major one, so placing a number d in box b will place a 1 in (matrix)column b*9+d +[81]+[81]+[81].
		81+81+81 are the first + second + third condition related columns.

		We have 81x4 = 324 condition columns at all.
		Hence, a 729x324 matrix is enough to transpose a sudoku problem into an exact cover one: */

	d := initDlxObj(324)

	// now add constraints that define sudoku rules.
	for r, i := 0, 0; r < 9; r++ {
		for c := 0; c < 9; c, i = c+1, i+1 {
			b := r/3*3 + c/3
			n := int(input[i] - '1')
			if n >= 0 && n < 9 {
				d.addRow([]int{i, 81 + r*9 + n, 162 + c*9 + n,
					243 + b*9 + n})
			} else {
				for n = 0; n < 9; n++ {
					d.addRow([]int{i, 81 + r*9 + n, 162 + c*9 + n,
						243 + b*9 + n})
				}
			}
		}
	}

	// run dlx
	d.searchAll()

	// extract the dlx solution.
	return d.totalSolution, d.solutionSet
}

func Solve(input string) string {

	/*	Condition 1: Cell taken
		The are 9x9 = 81 possible cells that can be taken (a cell is "taken" after you place a number in it) so first condition yields 81 (matrix)columns of (r,c) kind. R will be the major index for this condition.
		So, (matrix)columns from 1 to 9 will represent putting a number in row 1, columns 1 to 9.
		(Matrix)columns from 10 to 18 will represent putting a number in row 2, columns 1 to 9 and so on...
		Basically if you want to place a number in row r, column c you will place a 1 in column r*9+c.

		Condition 2: Row, digit condition
		There are 9 rows and 9 possible different numbers you can place in each row so, 9x9 = 81 and we have again 81 (matrix)columns for condition 2. Also this time r is being the major index so placing digit d in row r will place a 1 in (matrix)column r*9+d +[81].
		81 are the first condition related columns.

		Condition 3: Column, digit condition
		As for the rows, there are 9 columns with 9 possible different numbers you can place each one of them.
		Again, 9x9 = 81 (matrix)columns and this time the column index is the major one, so placing digit d in column c will place a 1 at (matrix)column c*9+d +[81]+[81].
		81+81 are the first + second condition related columns.

		Condition 4: Box, digit condition
		As for rows and columns, same for the boxes. 9 boxes, 9 digits, 81 more (matrix)columns. Box index is the major one, so placing a number d in box b will place a 1 in (matrix)column b*9+d +[81]+[81]+[81].
		81+81+81 are the first + second + third condition related columns.

		We have 81x4 = 324 condition columns at all.
		Hence, a 729x324 matrix is enough to transpose a sudoku problem into an exact cover one: */

	d := initDlxObj(324)

	// now add constraints that define sudoku rules.
	for r, i := 0, 0; r < 9; r++ {
		for c := 0; c < 9; c, i = c+1, i+1 {
			b := r/3*3 + c/3
			n := int(input[i] - '1')
			if n >= 0 && n < 9 {
				d.addRow([]int{i, 81 + r*9 + n, 162 + c*9 + n,
					243 + b*9 + n})
			} else {
				for n = 0; n < 9; n++ {
					d.addRow([]int{i, 81 + r*9 + n, 162 + c*9 + n,
						243 + b*9 + n})
				}
			}
		}
	}

	// run dlx
	d.search()

	// extract the dlx solution.
	return d.text()
}

// construct a DLX obj with all column headers
func initDlxObj(nCols int) *dlx {
	aCols := make([]header, nCols+1)

	// initialize root column
	root := &aCols[0]
	dlx := &dlx{aCols, root, nil, 0, nil}
	root.head = root
	root.left = &aCols[nCols].node
	aCols[nCols].right = &root.node

	tmpCols := aCols[1:]

	currCol := root

	// initialize the header link-list except root
	for i := range aCols[1:] {
		nextCol := &tmpCols[i]
		nextDlink := &nextCol.node

		nextCol.value = i
		nextCol.head = nextCol
		nextCol.up = nextDlink
		nextCol.down = nextDlink
		nextCol.left = &currCol.node

		currCol.right = nextDlink

		currCol = nextCol
	}

	dlx.totalSolution = 0
	dlx.solutionSet = make([]string, 0, 10)

	return dlx
}

func (d *dlx) addRow(newRow []int) {
	rlen := len(newRow)
	if rlen == 0 {
		return
	}
	allNodes := make([]node, rlen)

	for i, value := range newRow {
		header := &d.aCols[value+1]
		header.size++
		newNode := &allNodes[i]
		newNode.head = header
		newNode.up = header.up
		newNode.down = &header.node
		newNode.left = &allNodes[(i+rlen-1)%rlen]
		newNode.right = &allNodes[(i+1)%rlen]

		newNode.up.down, newNode.down.up, newNode.left.right, newNode.right.left = newNode, newNode, newNode, newNode
		newNode.row = &allNodes[0]

	}
}

// The original Knuth DLX algorithm
func (d *dlx) search() bool {

	rHead := d.root.right.head

	if d.root == rHead {
		return true
	}

	c := rHead

	for minSize := rHead.size; rHead != d.root; rHead = rHead.right.head {
		if rHead.size < minSize {
			c, minSize = rHead, rHead.size
		}
	}

	coverColumn(c)

	rlen := len(d.result)
	d.result = append(d.result, nil)

	for i := c.down; i != &c.head.node; i = i.down {
		d.result[rlen] = i
		for j := i.right; j != i; j = j.right {
			coverColumn(j.head)
		}
		if d.search() {
			return true
		}

		i = d.result[rlen]
		c = i.head

		for j := i.left; j != i; j = j.left {
			uncoverColumn(j.head)
		}

	}

	d.result = d.result[:len(d.result)-1]

	uncoverColumn(c)

	return false
}

// The original Knuth DLX algorithm
func (d *dlx) searchAll() bool {

	rHead := d.root.right.head
	if d.root == rHead {
		d.solutionSet = append(d.solutionSet, d.text())
		d.totalSolution++

		return true
	}

	c := rHead

	for minSize := rHead.size; rHead != d.root; rHead = rHead.right.head {
		if rHead.size < minSize {
			c, minSize = rHead, rHead.size
		}
	}

	coverColumn(c)

	rlen := len(d.result)
	d.result = append(d.result, nil)

	for i := c.down; i != &c.head.node; i = i.down {
		d.result[rlen] = i
		for j := i.right; j != i; j = j.right {
			coverColumn(j.head)
		}
		// if d.searchAll() {
		// 	return true
		// }
		d.searchAll()

		i = d.result[rlen]
		c = i.head

		for j := i.left; j != i; j = j.left {
			uncoverColumn(j.head)
		}

	}

	d.result = d.result[:len(d.result)-1]

	uncoverColumn(c)

	return false
}

// Covers one column (with Knuth DLX cover method) given the Header

func coverColumn(h *header) {

	// remove header
	h.right.left, h.left.right = h.left, h.right

	// remove node
	for i := h.down; i != &h.node; i = i.down {
		for j := i.right; j != i; j = j.right {
			j.down.up, j.up.down = j.up, j.down
			j.head.size--
		}
	}
}

// Uncovers one column (with Knuth DLX cover method) given the Header
func uncoverColumn(h *header) {

	// recover node
	for i := h.up; i != &h.node; i = i.up {
		for j := i.left; j != i; j = j.left {
			j.head.size++
			j.down.up, j.up.down = j, j
		}
	}

	// recover header
	h.right.left, h.left.right = &h.node, &h.node
}

// extracts result string
func (d *dlx) text() string {
	b := make([]byte, len(d.result))
	for _, r := range d.result {
		row := r.row
		b[row.head.value] = byte(row.right.head.value%9) + '1'
	}
	return string(b)
}
